package com.lyj.sc.SecondBruchToReview.Array20220719;

import java.util.ArrayList;
import java.util.List;

/**
 * @program: code-random
 * @description:
 * @author: lyj
 * @create: 2022-07-19 11:10
 * @version: 1.0
 * @Modifier By:
 **/
public class Solution {
    // 二分查找
    public int search(int[] nums, int target) {
        /// FIXME: 2022/7/19 二分法异常情况
        if (target < nums[0] || target > nums[nums.length - 1]) {
            return -1;
        }
        //找到不定量  左bi右bi
        int left=0;
        int right = nums.length-1;
        while (left<=right){
            int mid = left+((right-left)>>1);
            if(nums[mid]>target){
                right=mid-1;
            }else if(nums[mid]<target){
                left=mid+1;
            }else if(nums[mid]==target){
                return mid;
            }
        }
        return -1;
    }

    // 移除元素 双指针
    public int removeElement(int[] nums, int val) {
        int slowIndex=0;
        for (int fastIndex = 0; fastIndex < nums.length; fastIndex++) {
            if(nums[fastIndex]!=val){
                nums[slowIndex++]=nums[fastIndex];
            }
        }
        return slowIndex;
    }

    // 有序数组的平方 双指针
    public int[] sortedSquares(int[] nums) {
        int [] n = new int[nums.length];
        int d = nums.length-1;
        int left = 0 ,right = nums.length-1;
        while (left<=right){
            if (nums[left]*nums[left] < nums[right]*nums[right]){
                n[d--]=nums[right]*nums[right];
                right--;
            }else {
                n[d--]=nums[left]*nums[left];
                left++;
            }
        }
        return n;
    }

    // 长度最小的子数组 滑动窗口
    public int minSubArrayLen(int target, int[] nums) {
        //排序
        int l  = Integer.MAX_VALUE;
        int maxp = 0;
        int i = 0;
        for(int j = 0;j<nums.length;j++){
            maxp+=nums[j];
            //窗口内的值已经过大了
            while(maxp>=target){
                l=Math.min(l,j-i+1);
                maxp-=nums[i++];
            }
        }
        return l==Integer.MAX_VALUE? 0:l;
    }
    // 螺旋矩阵 II 坚持不变量 原则  左闭右开 或者 左开右闭
    public int[][] generateMatrix(int n) {
        int loop = 0;
        int [][] nums = new int[n][n];
        int startx = 0;
        int starty = 0;
        int count = 1;
        int start = 0;
        while(loop++ < n/2){  //循环 判断边界，从一开始

            //上 从左到右
            for(startx=start;startx<n-loop;startx++){
                nums[start][startx] = count++;
            }
            //右 从上到下
            for(starty=start;starty<n-loop;starty++){
                nums[starty][startx] = count++;
            }
            //左 从右到左
            for(;startx>=loop;startx--){
                nums[starty][startx] = count++;
            }
            //下 从下到上
            for(; starty>=loop ; starty--){
                nums[starty][startx] = count++;
            }
            start++;
        }
        if(n%2==1){
            nums[start][start]=count++;
        }
        return nums;
    }
    // 螺旋矩阵
    public List<Integer> spiralOrder(int[][] matrix) {
        ArrayList<Integer> list = new ArrayList<>();
        if(matrix==null||matrix[0].length==0||matrix.length==0){
            return list;
        }
        int rows = matrix.length-1;
        int coloum = matrix[0].length-1;
        int top=0,bottom=rows;
        int left=0,right=coloum;
        while (top<=bottom && left<=right){
            for (coloum=left;coloum<=right;coloum++){
                list.add(matrix[top][coloum]);
            }
            for (rows=top+1;rows<=bottom;rows++){
                list.add(matrix[rows][right]);
            }
            /// FIXME: 2022/7/19 top<bottom && left<right
            if(top<bottom && left<right){
                for (coloum=right-1;coloum>left;coloum--){
                    list.add(matrix[bottom][coloum]);
                }
                for (rows=bottom;rows>left;rows--){
                    list.add(matrix[rows][left]);
                }
            }
            top++;
            bottom--;
            left++;
            right--;
        }
        return list;
    }
}
